package storage.indexing.bTree;

import java.util.ArrayList;
import java.util.Hashtable;

import represent.type.Type;
import utils.Lib;
import config.Config;

/**
 * A <b>B+-tree</b> implementation
 * @author baiger
 *
 * @param <T> Key type
 */
public abstract class BTreeNode<T extends Type> {
	
	protected static final int POINTER_COUNT = Config.getInteger("BTreePointerCount", 4);
	protected static Hashtable<BTreeNode, BTree> rootTable = new Hashtable<BTreeNode, BTree>();
	
	protected T[] keys = (T[]) new Object[POINTER_COUNT - 1];
	// tuples specified by RecordID
	
	protected BTreeInternalNode<T> father;
	protected int size;
	
	/**
	 * Construct nodes other than the root
	 * @param father
	 */
	protected BTreeNode(BTreeInternalNode<T> father) {
		this.father = father;
		this.size = 0;
	}
	
	/**
	 * Constrct the root node
	 * @param tree
	 */
	protected BTreeNode(BTree tree) {
		this.father = null;
		this.size = 0;
		rootTable.put(this, tree);
	}
	
	protected abstract BTreeNode<T> createNode();
	
	protected abstract void update(BTreeNode<T> next, int pos);
	
	public void split(T key, int rid, BTreeNode<T> pointer) {
		Lib.assertTrue(size == POINTER_COUNT - 1);	// node is full
		// choose split point
		T splitPoint = keys[(size + 1) / 2];
		int pos = (size + 1) / 2;
		
		boolean flag = splitPoint.compareTo(key) < 0;
		if (flag) {
			splitPoint = keys[size / 2];
			pos = size / 2;
		}
		
		/* Create a new node and move half of the pointers into it.
		 * 
		 * Note: For internal nodes, splitPoint should be inserted as a key
		 * into the father node, rather than kept in the new (splitted) node. 
		 */
		BTreeNode<T> next = createNode();
		update(next, pos);	// a trick :D
		if (flag) {
			// insert into next node
			next.insert(key, rid, pointer);
		} else {
			// insert into this node
			this.insert(key, rid, pointer);
		}
		
		// split father
		if (father != null)
			// non-root node
			this.father.insert(splitPoint, -1, next);
		else {
			// root splitted
			BTree<T> tree = rootTable.remove(this);
			BTreeInternalNode<T> root = new BTreeInternalNode<T>(tree);
			tree.newRoot(root);
			rootTable.put(root, tree);

			// insert pointers into root
			root.insertFirst(this);
			father = root;
			
			root.insert(splitPoint, -1, next);
			next.father = root;
		}
	}
	
	public void merge(T key) {
	}
	
	protected abstract void insertKey(T key, int pos, int rid, BTreeNode<T> pointer);
	
	protected void insert(T key, int rid, BTreeNode<T> pointer) {
		if (size == POINTER_COUNT - 1) {
			split(key, rid, pointer);
		} else {
			for (int i = 0; i < size; ++i) {
				if (keys[i].compareTo(key) > 0) {
					insertKey(key, i, rid, pointer);
					return;
				}
			}
			// insert into the last position
			insertKey(key, size + 1, rid, pointer);
		}
	}
	
	protected abstract void deleteKey(T key, int pos, int rid);
	
	public void delete(T key, int rid) {
		// TODO: correctly fill this method
		for (int i = 0; i < size; ++i)
			if (keys[i].equals(key)) {
				deleteKey(key, i, rid);
				if (size == 0)
					father.delete(this);
				if (size <= POINTER_COUNT / 2 - 1)
					merge(keys[1]);
				return;
			}
		// no such key
	}

}